/**
 * 24. 两两交换链表中的节点
 * https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/
 */
public class Solutions_24 {
    public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 4};  // output: {2, 1, 4, 3}
        int[] arr = {1, 2, 3, 4, 5};  // output: {2, 1, 4, 3, 5}

        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        ListNode result = swapPairs2(head);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    /**
     * 解法一：递归
     * 自底向上
     */
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;  // 前一节点
        ListNode second = head.next;  // 后一节点

        // 递归 second 的下一节点，最终返回的就是以 second.next 为头结点的完成了两两交换的链表
        // 返回结果作为 first 节点的下一节点
        first.next = swapPairs(second.next);

        // 后一节点的下一节点，为前一节点，完成交换
        second.next = first;
        return second;
    }

    /**
     * 解法二：迭代
     * 自顶向下
     */
    public static ListNode swapPairs2(ListNode head) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        cur.next = head;

        while (head != null && head.next != null) {
            // 临时记录，下一遍历结点为当前结点的下一结点的下一结点
            ListNode temp = head.next.next;
            // 先记录下一结点
            cur.next = head.next;
            cur = cur.next;
            // 再记录当前结点
            cur.next = head;
            cur = cur.next;
            head = temp;
        }
        // 循环结束后，拼接上最后一个结点或将下一结点置空（若不加上最后一个结点，会出现环）
        // 结点数量为奇数时，最后一个结点为结点对象，结点数量为偶数时，最后一个结点为 null
        cur.next = head;
        return res.next;
    }
}
